package unit11;

import java.util.Arrays;

public class QuickSortDemo {
    public static void main(String[] args) {
//		int[] arr = { 5, 2, 7, 8, 9, 1 };
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100 + 1);
        }
		System.out.println("排序前：" + Arrays.toString(arr));
        long start = System.currentTimeMillis();
        quickSort(arr, 0, arr.length-1);
		System.out.println("排序后：" + Arrays.toString(arr));
        long end = System.currentTimeMillis();
        System.out.println("共花费" + (end - start) + "毫秒");

    }
    //我们默认的是以每趟序列的第一个数为基准
    public static void quickSort(int[] arr,int left,int right){
        int temp = 0;  // 基准
        int l = left;   // 初始化最左边的元素的索引
        int r = right;  // 初始化最右边的元素的索引
        if(left<right){
            //我们将这个数组中的第一个数赋值给temp。
            temp = arr[left];   //temp相当于我们的基准，数列的第一个数
            while(l!=r){   //我们假定，当l=r的时候退出该循环
                //开始的时候，我们从最右边开始找元素，当我们找的元素的值大于等于我们的基准，那么我们将它向左移，直到这个元素的值小于基准为止。
                while(r>l && arr[r]>=temp){
                    --r;
                }
                //此时arr[r]已经小于temp，这个时候我们需要进行一个判断，看看是否还是符合l<r，如果符合的话，我们将arr[r]这个值，直接赋值到左边(数组的第一个值)
                //并且让我们左边的l指向下一个位置。
                if(l<r){
                    arr[l] = arr[r];
                    ++l;
                }
                //在右边换过来之后，我们需要交叉得变换，这个时候我们从左边开始比较
                //前提还是l<r，只不过由于我们在左边开始，所以我们需要判断arr[l]如果小于temp的值，那么我们应该继续向右移，以知道大于等于temp的值为止。
                while(l<r && arr[l]<temp){
                    ++l;
                }
                ////此时arr[l]已经大于或者等于temp，这个时候我们需要进行一个判断，看看是否还是符合l<r，如果符合的话，我们将arr[l]这个值，直接赋值到右边(r所在的位置)
                //并且让我们右边的r指向下一个位置。
                if(l<r){
                    arr[r] = arr[l];
                    --r;
                }
            }
            //在执行完上面的循环之后，我们除了基准的位置的空的外，基准左边的都小于它，基准右边的都大于它，形成了一个相对有序的序列，
            //最终我们把之前赋值的temp加入到arr[l]中(因为这个时候r=l)
            arr[l] = temp;
            //执行完上面的依次循环之后，我们需要对子序列进行在依次的快速排序，执行过程与上面的相同。
            quickSort(arr, left, l-1);
            quickSort(arr, l+1, right);
        }
    }
}
